package com.tree.leetcode;

import java.util.HashMap;

/**
 * package com.tree.leetcode
 * description:
 *
 * @author tree
 * @date 2020-04-01 10:40
 */

class Node {
    public Node(String key, String value) {
        this.key = key;
        this.value = value;
    }

    public Node pre;
    public Node next;
    public String key;
    public String value;
}

public class LRUCache2 {
    private Node head;
    private Node end;
    //缓存上限
    private int limit;
    private HashMap<String, Node> map;

    public LRUCache2(int limit) {
        this.limit = limit;
        map = new HashMap();
    }

    public String get(String key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        //调整node到尾部
        refreshNode(node);
        return node.value;
    }

    public void put(String key, String value) {
        Node node = map.get(key);
        if (node == null) {
            //key不存在直接插入
            while (map.size() >= limit) {
                //去除链表内的节点
                String oldKey = removeNode(head);
                //去除map中的缓存
                map.remove(oldKey);
            }
            node = new Node(key, value);
            //链表中加入节点
            addNode(node);
            //map中加入节点
            map.put(key, node);
        } else {
            //更新节点并调整到尾部
            node.value = value;
            refreshNode(node);
        }
    }

    private void refreshNode(Node node) {
        //如果访问的是尾节点，无须移动节点
        if (node == end) {
            return;
        }
        //把节点移动到尾部，相当于做一次删除插入操作
        removeNode(node);
        addNode(node);
    }

    private String removeNode(Node node) {
        //尾节点
        if (node == end) {
            end = end.pre;
        } else if (node == head) {
            //头结点
            head = head.next;
        } else {
            //中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    private void addNode(Node node) {
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        end = node;
        if (head == null) {
            head = node;
        }
    }

    public static void main(String[] args) {
        LRUCache<Node> cache = new LRUCache<>(4);
        Node node1 = new Node("key1", "1");
        Node node2 = new Node("key2", "2");
        Node node3 = new Node("key3", "3");
        Node node4 = new Node("key4", "4");
        Node node5 = new Node("key5", "5");
        cache.put("key1", node1);
        cache.put("key2", node2);
        cache.put("key3", node3);
        cache.put("key4", node4);
        cache.get("key2");
        cache.put("key5", node5);
        cache.get("key2");

        LRUCache2 cache2 = new LRUCache2(4);
        cache2.put("key1","1");
        cache2.put("key2","2");
        cache2.put("key3","3");
        cache2.put("key4","4");
        cache2.get("key2");
        cache2.put("key5","5");
        cache2.get("key2");
    }
}
